package leetcode;

/**
 * @author ht
 * @create 2025-06-18 21:36
 * @desc
 **/
public class T209 {


    /**
     * 暴力写法，双层遍历，在第二层遍历中，如果sum>=target，跳出此次遍历，进行剪枝，由于数据流是10的5次方，因此使用n方暴力算法会超时
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {

        int maxLen = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if(sum >= target) {
                    maxLen = Math.min(maxLen, j - i + 1);
                    break;
                }
            }
        }
        return maxLen == Integer.MAX_VALUE ? 0 : maxLen;
    }


    /**
     * 浮动窗口写法
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen2(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= target) {
                minLen = Math.min(minLen, i - left + 1);
                sum -= nums[left++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 :minLen;
    }
}
